package com.ronz.sort;

import java.util.Arrays;

/**
 * @Description 快速排序
 * @Author Ronz
 * @Date 2021/1/10 19:00
 * @Version 1.0
 */
public class No5_QuickSort {

    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};

//         int pivot = partition(arr, 0, arr.length - 1);
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @Description 將序列分片，基准元素左边的都是小于它的，右边的都是大于它的
     * @Param [arr, left, right]
     * @return int
     */
    public static int partition(int[] arr, int left, int right){
        int key = arr[left];        // 基准元素
        while(left<right){
            /* 先从右往移动，直到遇见小于 key 的元素 */
            while (left<right && arr[right]>=key){
                right--;
            }
            arr[left] = arr[right];         // 填坑
            /* 再从左往右移动，直到遇见大于 key 的元素 */
            while(left<right && arr[left]<=key){
                left++;
            }
            arr[right] = arr[left];         // 填坑

        }
        arr[left] = key;            // 填坑
        return left;
    }

    public static void quickSort(int[] arr, int left, int right){
        if (left < right){
            // 把数组分块
            int pivot = partition(arr, left, right);
            System.out.println(Arrays.toString(arr));
            // 左边递归
            quickSort(arr, left, pivot-1);
            // 往右递归
            quickSort(arr, pivot+1, right);
        }
    }

}
